package com.srunpass.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author srunpass
 * @version Id: 单词拆分II, v 0.1 2024/6/26 18:49 srunpass Exp $
 */
public class 单词拆分II {

    List<String> res = new ArrayList<>();
    Set<String> words;
    String s;

    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s;
        words = new HashSet<>(wordDict);
        gene("", 0);
        return res;
    }

    private void gene(String sent, int index) {
        if (index == s.length()) {
            res.add(sent);
        }
        for (int i = index + 1; i <= s.length(); i++) {
            String word = s.substring(index, i);
            if (words.contains(word)) {
                if (!sent.isEmpty()) {
                    word = sent + " " + word;
                }
                gene(word, i);
            }
        }
    }

}
